package com.lg.algorithm.leetcode.dt;

/**
 * 泰波那契序列 Tn 定义如下： 
 *
 * T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
 *
 * 给你整数 n，请返回第 n 个泰波那契数 Tn 的值
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/n-th-tribonacci-number
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class TaiBoNaQie {

    public static void main(String[] args) {

        System.out.println(fei(0));
        System.out.println(fei(1));
        System.out.println(fei(2));
        System.out.println(fei(3));
        System.out.println(fei(4));
        System.out.println(fei(5));

        System.out.println(fei(25));
    }

    public static  int fei(int n){
        if (n == 0) {
            return 0;
        }
        if (n < 3) {
            return 1;
        }

        int q = 0;
        int w = 1;
        int e = 1;
        int r = 2;

        for (int i = 3; i <=n; i++) {
            r = q + w + e;
            q = w;
            w = e;
            e = r;
        }


        return r;
    }


}


